
class Solution {

    /**
     * 最小覆盖子串
     * https://leetcode.cn/problems/minimum-window-substring/
     * 时间复杂度：O（N）
     * 空间复杂度：O（m + n)
     */
    public String minWindow(String ss, String tt) {
        //预处理
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        char[] hash1 = new char[128];
        char[] hash2 = new char[128];

        int kinds = 0,minLen = Integer.MAX_VALUE,begin = -1;

        for(char c : t) if(hash1[c]++ == 0) kinds++;

        //滑动窗口
        for(int left = 0,right = 0,count = 0;right < s.length;right++){
            //1.进入窗口
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;

            //2.判断
            while(count == kinds){
                //3.更新结果
                if(right - left + 1 < minLen){
                    begin = left;
                    minLen = right - left + 1;
                }

                //4.出窗口
                char out = s[left++];
                if(hash1[out] == hash2[out]--) count--;
            }
        }
        //返回
        return begin == -1 ? new String() : ss.substring(begin,minLen + begin);
    }

    /**
     * 二分查找
     * https://leetcode.cn/problems/binary-search/
     * 时间复杂度：O（logN)
     * 空间复杂度：0（1）
     */

    public int binarySearch(int[] arr , int target){
        //模板
        int left = 0,right = arr.length - 1;
        //1.循环的终止条件：left > right ,左右下标相等也需要判断
        while(left <= right) {
            //2.三种情况：大于，小于，等于
            int mid = left + (right - left) + 1;
            if(target > arr[mid]){
                left = mid + 1;
            }else if(target < arr[mid]){
                right = mid - 1;
            }else {
                return arr[mid];
            }
        }
        return -(left + 1);
    }

    /**
     * 二分查找最大区间
     * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
     * @param nums   数组
     * @param target 目标值
     * @return 范围数组
     */
        public int[] searchRange(int[] nums, int target) {
            int[] ret = new int[2];

            ret[0] = -1;
            ret[1] = -1;

            if(nums.length == 0) return ret;

            //1.二分左端点
            int left = 0,right = nums.length - 1;
            //*循环的条件
            while(left < right){
                //求中点下标
                int mid = left + (right - left) / 2;

                if(nums[mid] < target) left = mid + 1;
                else right = mid;
            }

            //判断一下
            if(nums[left] == target) ret[0] = left;
            else return ret;

            //2.二分求右端点
            left = right;right = nums.length - 1;
            while(left < right){
                int mid = left + (right - left + 1) / 2;

                if(target < nums[mid]) right = mid - 1;
                else left = mid;
            }
            ret[1] = right;
            return ret;
        }
}